package demo1;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    public int removeDuplicates(int[] nums) {
        if (nums.length < 3) {
            return nums.length;
        }

        int size = 0;
        int cur = Integer.MIN_VALUE;
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == cur) {
                cnt++;
            } else {
                cur = nums[i];
                cnt = 1;
            }
            if (cnt > 2) {
                continue;
            }
            nums[size++] = nums[i];
        }
        return size;
    }

    public int numberOfGoodSubsets(int[] nums) {
        int[] count = new int[31];
        for(int i = 0 ; i < nums.length ; i++){
            count[nums[i]]++;
        }
        int[] n1 = {2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30};
        int[][] n2 = {{2},{3},{5},{2,3},{7},{2,5},{11},{13},{2,7},{3,5},{17},{19},{3,7},{2,11},{23},{2,13},{29},{2,3,5}};
        List<Integer> plan = new ArrayList<>();
        for(int i = 0 ; i < 18 ; i++){
            findPlan(0,n1,n2,i,0,plan);
        }
        int base = 1000000007;
        long ans = 0;
        for(Integer i : plan){
            long temp = 1;
            for(int j = 0 ; j < 18 ; j++){
                if( ((i >> j) & 1) == 1){
                    temp *= (count[n1[j]] % base);
                    temp %= base;
                }
            }
            ans += temp;
            ans %= base;
        }
        for(int i = 0 ; i < count[1] ; i++){
            ans = (ans*2)%base;
        }
        return (int)ans;
    }

    public void findPlan(int state, int[] n1, int[][] n2, int index, int plan, List<Integer> plans){
        int[] nums = n2[index];
        for(int i = 0 ; i < nums.length ; i++){
            if(((state>>(nums[i]-1)) & 1) == 1){
                return;
            }else{
                state += (1 << (nums[i]-1));
            }
        }
        plan += (1 << index);
        plans.add(plan);
        for(int i = index+1 ; i < n1.length ; i++){
            findPlan(state,n1,n2,i,plan,plans);
        }
    }
}
